package test6;

import java.util.*;

public class Solution3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入哈夫曼树的结点个数：");
        int size = sc.nextInt();
        System.out.println("请输入哈夫曼树的权值和数据：");
        int[] weight = new int[size];
        String[] value = new String[size];
        for (int i = 0; i < size; i++) {
            weight[i] = sc.nextInt();
            value[i] = sc.next();
        }
        TreeNode root = createHuffmanTree(weight, value);
        showTree(root);
        encoding(root);
    }

    public static TreeNode createHuffmanTree(int[] weight, String[] value) {
        PriorityQueue<TreeNode> nodes = new PriorityQueue<>();
        for (int i = 0; i < weight.length; i++) {
            TreeNode node = new TreeNode(weight[i], value[i]);
            nodes.add(node);
        }
        TreeNode parent;
        while (nodes.size() > 1) {
            //取出最小的两个结点
            TreeNode leftNode = nodes.poll();
            TreeNode rightNode = nodes.poll();
            //构建新的二叉树
            parent = new TreeNode(leftNode.weight + rightNode.weight, "-");
            parent.left = leftNode;
            parent.right = rightNode;
            nodes.add(parent);
        }
        return nodes.poll();
    }

    public static void encoding(TreeNode node){
        if (!"-".equals(node.value)){
            System.out.println("数据" + node.value + "的哈夫曼编码：" + node.huffmanCode);
            return;
        }
        if (node.left != null){
            node.left.huffmanCode = node.huffmanCode + "0";
            encoding(node.left);
        }
        if (node.right != null){
            node.right.huffmanCode = node.huffmanCode + "1";
            encoding(node.right);
        }
    }

    static int h = 0;
    public static void showTree(TreeNode node){
        if (node != null){
            for (int i = 0; i < h; i++) {
                System.out.print("#");
            }
            System.out.println(node.value);
            h++;
            showTree(node.left);
            showTree(node.right);
            h--;
        }
    }
}

class TreeNode implements Comparable{
    int weight;
    String value;
    TreeNode left;
    TreeNode right;

    String huffmanCode = "";


    public TreeNode(int weight, String value){
        this.weight = weight;
        this.value = value;
    }

    @Override
    public int compareTo(Object o) {
        if (o instanceof TreeNode){
            TreeNode treeNode = (TreeNode) o;
            //从小到大排序
            return this.weight - treeNode.weight;
        }
        return 0;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "weight=" + weight +
                ", value='" + value + '\'' +
                '}';
    }
}
